def infix_to_postfix(infix_expr: str) -> str:
    """中缀表达式转后缀表达式"""
    prec = {"*": 3, "/": 3, "+": 2, "-": 2, "(": 1}

    from pythonds.basic import Stack

    op_stack = Stack()

    postfix_list = []

    token_list = [v for v in infix_expr if v != " "]

    from string import ascii_letters

    for token in token_list:
        if token in ascii_letters:
            postfix_list.append(token)
        elif token == "(":
            op_stack.push(token)
        elif token == ")":
            top_token = op_stack.pop()
            while top_token != "(":
                postfix_list.append(top_token)
                top_token = op_stack.pop()
        else:
            while (not op_stack.empty()) and (prec[op_stack.top()] >= prec[token]):
                postfix_list.append(op_stack.pop())
            op_stack.push(token)

    while not op_stack.empty():
        postfix_list.append(op_stack.pop())

    return "".join(postfix_list)


def do_math(op, op1, op2):
    if op == "*":
        return op1 * op2
    elif op == "/":
        return op1 / op2
    elif op == "+":
        return op1 + op2
    else:
        return op1 - op2


def postfix_eval(postfix_expr: str):
    from pythonds.basic import Stack

    op_stack = Stack()

    for token in postfix_expr:
        if token in "0123456789":
            op_stack.push(int(token))
        else:
            op2 = op_stack.pop()
            op1 = op_stack.pop()
            ret = do_math(token, op1, op2)
            op_stack.push(ret)

        return op_stack.pop()
